//
// Description: 51. N皇后
// Created by Loading on 2021/1/23.
//

#include <bits/stdc++.h>

using namespace std;

vector<string> combination(const vector<int> &queens, int n) {
    vector<string> v;
    for (int i = 0; i < n; ++i) {
        string s(n, '.');
        s[queens[i]] = 'Q';//queens数组标记哪一列放置皇后
        v.push_back(s);
    }

    return v;
}

void Backtracking(vector<vector<string>> &res, vector<int> &queens, unordered_set<int> &cols,
                  unordered_set<int> &diagonals1,
                  unordered_set<int> &diagonals2,
                  int n,
                  int row) {
    if (row == n) {//一轮遍历结束，组合当前case并回溯
        res.push_back(combination(queens, n));
    } else {
        for (int i = 0; i < n; ++i) {
            if (cols.find(i) != cols.end()) {//此列存在皇后
                continue;
            }
            int dia1 = row + i;
            if (diagonals1.find(dia1) != diagonals1.end()) {//左对角线存在皇后
                continue;
            }
            int dia2 = row - i;
            if (diagonals2.find(dia2) != diagonals2.end()) {//右对角线存在皇后
                continue;
            }
            queens[row] = i;//满足条件，放置皇后
            cols.insert(i);
            diagonals1.insert(dia1);
            diagonals2.insert(dia2);
            Backtracking(res, queens, cols, diagonals1, diagonals2, n, row + 1);//递归，向后寻找
            //递归完毕，重置标记
            queens[row] = -1;
            cols.erase(i);
            diagonals1.erase(dia1);
            diagonals2.erase(dia2);
        }
    }
}

vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> res;
    vector<int> queens(n, -1);

    //列，两侧对角线 标记
    unordered_set<int> cols;
    unordered_set<int> diagonals1;
    unordered_set<int> diagonals2;
    //回溯算法
    Backtracking(res, queens, cols, diagonals1, diagonals2, n, 0);

    return res;
}

int main() {
    int n = 9;//皇后数量
    vector<vector<string>> vec;
    vec = solveNQueens(n);
    for (const auto &v : vec) {
        cout << '[';
        for (const auto &s : v) {
            cout << s << endl;
        }
        cout << ']' << endl;
    }
}

